#ifndef TARJAN_H_INCLUDED
#define TARJAN_H_INCLUDED
#include "CGraph.h"
template <typename GraphType>
class SCCTarjan
{
public:

    SCCTarjan() {};
    ~SCCTarjan() {};

    vector<vector<int>> Process(const GraphType* _graph);
    void DFS(int u);

private:

    const GraphType* graph;
    vector<bool> visited;           // посещенность вершин во время DFS
    stack<int> DFSStack;            // стек для DFS
    int time;
    vector<int> lowLink;            // хранит вершину с наименьшим индексом, достижимую из данной
    vector<vector<int>> components; // храние компоненты сильной связности
};

template <typename GraphType>
vector<vector<int>> SCCTarjan<GraphType>::Process(const GraphType* _graph)
{
    graph = _graph;
    int n = graph->GetVertexCount();
    visited.resize(n, 0);
    time = 0;
    lowLink.resize(n, 0);

    for (int u = 0; u < n; ++u)
    {
        if (!visited[u])
        {
            DFS(u);
        }
    }

    return components;
}

template <typename GraphType>
void SCCTarjan<GraphType>::DFS(int u)
{
    lowLink[u] = time++;
    visited[u] = true;
    DFSStack.push(u);
    bool isComponentRoot = true;

    for (int i = u * graph->GetVertexCount();
    i != (u + 1) * graph->GetVertexCount(); ++i)
    {
        if (!graph->existsEdge(i)) continue;

        int v = i % graph->GetVertexCount();

        if (!visited[v])
        {
            DFS(v);
        }

        if (lowLink[u] > lowLink[v])
        {
            lowLink[u] = lowLink[v];
            isComponentRoot = false;
        }
    }

    if (isComponentRoot)
    {
        vector<int> component;
        while (true)
        {
            int x = DFSStack.top();
            DFSStack.pop();
            component.push_back(x);
            lowLink[x] = numeric_limits<int>::max();
            if (x == u)
            {
                break;
            }
        }
        components.push_back(component);
    }
}


#endif // TARJAN_H_INCLUDED
